题意简述
给定一个序列，长度。定义一个区间的得分为这段区间内不同的数的个数。请你将这个序列划分成段，使得每段的分数加起来最大。
思路
设表示前个分成了段的最大得分和，表示内不同的数个数，那么
（这里不知为啥公式爆了，看图凑合一下），其中枚举前面的一个点（即）。
珂是这个转移大概是的，完全不能承受。
观察数据范围，发现时间复杂度大概是，或者带个，根号之类的。
不能用状态数优化这个，那就考虑用数据结构优化。发现只和有关（这就是为什么我把放到了第一维而不是第二维）。
那么依赖的状态就只有一个序列了。然后我们就是要求这个序列的整体最大值，其中第个点的权值是。
我们珂以把这个东西想象成这样：初始每个点都是，然后通过一些修改操作（区间加）变成。
这样考虑，设表示：上一次出现的位置。（如果没有上一次，那么）那么，对于一个种类，它的贡献就是把区间。然后点的值就是之间加上值的最大值了。
这个维护区间种类数的方式十分常见！！！请各位记好这个trick！！！
（然后解释一下为什么是这样的，如果你能想明白，跳过）
假设序列是这样的：1
1 5 2 1 4 5
易得数组是这样的：1
1 1 1 2 1 3
然后我们考虑第一个位置。区间加，也就是。
然后就是区间加
加完之后我们发现区间变成了这样：1
5 4 3 2 1 1
其中这个序列的第个位置表示（是最后一个位置）中有多少不同的种类。
区间加的意义是：在区间内，每个位置到末尾都能包含
区间加的意义是：在区间内，每个位置到末尾都能包含
…
区间加的意义是：在区间内，每个位置到末尾都能包含
也许你会说：那第一个位置到最后一个位置不是也能包含么，但是这一段在算上一个和相同的数（即）的时候，已经被加过了。如果再加一次，就重复了。
（也就是说，只加到这一段保证了不会重复，而且也不可能会有遗漏）
（顺便说一句，举一个实例解释问题是很有效的）
然后我们发现，我们珂以拿线段树维护这个东西。对于一个，初始值是，然后区间加即可，最后的值就是查询区间的最大值。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using namespace std;
namespace Flandre_Scarlet
{
int n,k,a[N];
void R1(int &x)
{
x=0;char c=getchar();int f=1;
while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=(f==1)?x:-x;
}
void Input()
{
R1(n),R1(k);
F(i,1,n) R1(a[i]);
}
int dp[51][N];
class SegmentTree
{
public:
struct node
{
int l,r;
int s,a;
}tree[N<<2];
void Update(int index)
{
S=max(lS,rS);
}
void Build(int pos,int l,int r,int index)
{
L=l,R=r,S=0,A=0;
if (l==r)
{
S=dp[pos][l-1];
return;
}
int mid=(l+r)>>1;
Build(pos,l,mid,ls);
Build(pos,mid+1,r,rs);
Update(index);
}
void AddOne(int x,int index)
{
S+=x;A+=x;
}
void PushDown(int index)
{
if (A)
{
AddOne(A,ls);
AddOne(A,rs);
A=0;
}
}
void Add(int l,int r,int x,int index)
{
if (l>R or L>r) return;
if (l<=L and R<=r) return AddOne(x,index);
PushDown(index);
Add(l,r,x,ls);
Add(l,r,x,rs);
Update(index);
}
int Query(int l,int r,int index)
{
if (l>R or L>r) return 0;
if (l<=L and R<=r) return S;
PushDown(index);
return max(Query(l,r,ls),Query(l,r,rs));
}
}T;
int pos[N];
int pre[N];
void Soviet()
{
F(i,1,n)
{
pre[i]=pos[a[i]]+1;
pos[a[i]]=i;
}
F(i,1,k)
{
T.Build(i-1,1,n,1);
F(j,1,n)
{
T.Add(pre[j],j,1,1);
dp[i][j]=T.Query(1,j,1);
}
}
printf("%d\n",dp[k][n]);
}
void IsMyWife()
{
Input();
Soviet();
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
return 0;
}